This invention relates to the field of computer systems. More particularly, a system and methods are provided for preventing the starvation of a packet or other communication queued for action (e.g., transmission).
In many computing environments, a communication interface (e.g., a network interface card, a channel adapter) maintains multiple queues of outbound packets, cells, frames or other communications. The communication interface is responsible for scheduling or preparing the communications for transmission, but must adhere to any applicable constraints. Depending on the type of communications, their destination, the status of the transmission network (e.g., whether it is congested), and so on, multiple constraints may be placed on individual communications, thereby delaying their transmission or preparation for transmission.
For example, a communication may be subject to constraints associated not only with the destination of the communication, but also the route or link(s) between the origination and destination. In particular, a constraint regarding the communication's destination may depend upon the status of the destination (e.g., whether it has room for the communication, whether a delay is required before sending the communication), while a constraint regarding the communication's route of travel may reflect congestion within one or more physical links the communication must traverse.
When multiple interfering constraints are applied to a system, they may cause arbitrary delays in scheduling a communication for transmission. Thus, even if a packet is cleared for its next hop by the recipient of that hop, it cannot be scheduled if the final destination has not approved it, and vice versa.
In general, whenever there are multiple sources (e.g., queues) of outgoing communications, and a communication may be subject to multiple constraints, those constraints may interfere with one another, thereby introducing undesirable delay. In existing communication interfaces, it is possible that a communication may be denied transmission for an indeterminate period of time or, alternatively, a communication link may be underutilized in an effort to avoid starving the communication.
Therefore, what is needed is a system and method for efficiently scheduling communications for transmission on a shared link, while promoting maximum usage of the link's bandwidth and without delaying any individual communication for an unbounded period of time.